import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
解题思路：中序非递归遍历需要借助栈
 1. 空树，直接返回
 2. 如果树非空：从根节点位置开始遍历，但此时根节点不能遍历，因为中序遍历规则：左子树、根节点、右子树
      a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈
      b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，可以直接遍历该节点，对于该节点，          其左子树已经遍历，该节点也已经遍历，剩余其右子树没有遍历，将其左子树当成一棵新的树开始遍            历，继续a
具体实现：参考代码，学生自己动手画图理解
*/
class Solution1 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        // 空树直接返回
        if(null == root){
            return ret;
        }
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        while(null != cur || !s.empty()){
            // 沿这cur一直往左侧走，找到该条路径中最左侧的节点，并保存其所经路径中的所有节点
            while(null != cur){
                s.push(cur);
                cur = cur.left;
            }
            // 获取根节点，直接遍历，因为其左侧是空树
            cur = s.peek();
            s.pop();
            ret.add(cur.val);
            // cur的左子树已经遍历，cur已经遍历，剩余其右子树没有遍历，
            // 将其右子树当成一棵新的树进行遍历
            cur = cur.right;
        }
        return ret;
    }
}